package 力扣.双指针.最长区间;

import java.util.Arrays;

public class 替换后的最长重复字符424 {
    public static void main(String[] args) {
//           String s = "AABCABBB";
//           String s = "ABADE";
           String s = "BAAA";
        int i = characterReplacement2(s, 0);
        System.out.println(i);
    }

    /**
     * 双指针（滑动窗口）
      原理：开辟左右两个指针left、right。right指针先右移，找到在区间[left,right]最多的字符的个数，
           然后计算在当前区间中剩余其他字符的个数:如果大于k(题目中的可替换个数)，则让left指针右移，以保证当前区间
           中剩余字符的个数总是小于k。
           最后直到right到达字符串末尾，然后当前区间的长度就是结果。
      补充：因为字符串中仅包含大写字母，我们可以使用长度为26的数组来记录每一个字母出现的次数。
     */
    public static int characterReplacement(String s, int k) {
        int[] nums = new int[26];
        int left = 0 , right = 0;//开辟左右指针
        int maxAn = 0;//当前区间中，最多字符的个数
        while (right < s.length()){//直到right指针到达末尾
            char c = s.charAt(right);
            nums[c - 'A']++;//记录每个字符出现的个数
            maxAn = Math.max(maxAn, nums[c - 'A']);
            if ( (right - left + 1 - maxAn) > k  ){//'right - left + 1 - maxAn'表示剩余其他字符的个数（n）,若窗口不满足题意，则left指针开始右移，以保证窗口符合题意
                nums[s.charAt(left) - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;//当前区间即为结果
    }

    /**
     * 双指针：最长区间问题
     * 需要在滑动窗口中寻找出现次数最多的那个字符（即主力字符）
     *   如何寻找主力字符呢？只有当前右指针指向的这个当前字符才有可能是主力字符
     * 左指针何时移动？
     *   坏了才移动原则，当新字符加入之后，如果除了主力字符，其他字符的数量超过替换字符K,则left就可以移动了。
     *   只需移除一个元素即可。
     * @param s
     * @param k
     * @return
     */
    public static int characterReplacement2(String s, int k) {
        if (s == null || s.length() == 0){
            return 0;
        }
        if (s.length() <= k){
            return k;
        }
        int[] nums = new int[26];//
        int left = -1;
        int ans = 0;
        int teMaxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            nums[c - 'A']++;
            teMaxLen = Math.max(teMaxLen, nums[c - 'A']);
            if (i - left - teMaxLen > k){
                nums[s.charAt(++left) - 'A']--;
                // left++;
            }
            ans = Math.max(ans, i - left);
        }
        return ans;
    }

    public int characterReplacement3(String s, int k) {
         if (s == null || s.length() == 0){
             return 0;
         }
         int[] nums = new int[26];
         final int N = s.length();
         int left = -1;
         int maxTe = 0;
         int ans = 0;
        for (int i = 0; i < N; i++) {
            char c = s.charAt(i);
            nums[c - 65]++;
            maxTe = Math.max(nums[c - 65],maxTe);//区间中最长元素个个数
            if (i - left - maxTe > k){
                nums[s.charAt(++left) - 65]--;
            }
            ans = Math.max(ans, i - left);

        }
        return ans;
    }


}
